package exam.microsoft.second.task2;

import java.util.Arrays;

class Solution {
    public int solution(int[] A, int M) {
        if (A.length < 2)
            return A.length;
        int[] cnt = new int[A.length];
        Arrays.fill(cnt, 1);
        Arrays.sort(A);
        int res = 1;
        for (int i=1; i<A.length; ++i) {
            int j = i-1;
            while (j >= 0 && (A[i] - A[j]) % M != 0)
                --j;
            if (j >= 0)
                cnt[i] = cnt[j] + 1;
            res = Math.max(res, cnt[i]);
        }
        return res;
    }
}
